package com.linwen.excise.leetcode;

/**
 * @ClassName _lcp12
 * @Description TODO
 * @Author zero
 * @DATE 2024/4/4 9:53 AM
 * @Version 1.0
 */
public class _lcp12 {
    public static void main(String[] args) {
        int[] time = {1,2,3,3};
        int m = 2;
        System.out.println(minTime(time,m));
    }

    public static int minTime(int[] time, int m) {
        if(m>time.length){// 一天一题且求助，花费0
            return 0;
        }
        int min = 0;
        int max = 0;
        for (int i = 0; i < time.length; i++) {
            max += time[i];
        }
        while (min<max){
            int mid = min+(max-min)/2;
            if(check(time,m,mid)){
                max = mid;
            }else {
                min = mid+1;
            }
        }
        return min;
    }

    private static boolean check(int[] time, int m, int mid) {
        int helpCount = 0;
        int days = 0;
        int max = time[0];
        int canCost = mid;
        for(int i = 0;i<time.length;){
            max = Math.max(max,time[i]);
            if(canCost>=time[i]) {// 可以刷题
                canCost -= time[i];
                i++;
            }else { // 时间不够了，可能需要求助
                if(helpCount==0){ // 求助次数还没用
                    canCost += max;
                    helpCount++;
                    if(canCost>=time[i]){// 找到最大的那个时间求助
                        canCost -= time[i];
                        i++;
                    }else {// 只能明天了
                        helpCount = 0;
                        canCost = mid;
                        max = time[i];
                        days++;
                        if(days>=m){
                            return false;
                        }
                    }
                }else {// 无法求助，只能下一天再做
                    helpCount = 0;
                    canCost = mid;
                    max = time[i];
                    days++;
                    if(days>=m){
                        return false;
                    }
                }
            }
        }
        return true;
    }
}
